12317. Field modulo
For the given integers a, b,
c, n, p, find the value of the expression:
Print the result as two numbers x and y
such that
Input. Five integers a, b,
c, n, p. It
is known that:
·
p is a prime number,
·
0 ≤ a, b
< p,
·
1
≤ c < p,
·
0 ≤ n ≤
1018
Output. Print two integers x and y – the coefficients of 1 and 
respectively,
modulo p.
|
Sample input 1 |
Sample output
1 |
|
2 1 5 2 17 |
9 4 |
|
|
|
|
Sample input 2 |
Sample output
2 |
|
3 2 5 10 17 |
1 2 |
SOLUTION
combinatorics
Algorithm analysis
All computations should be
performed in the extended field:
Operation rules:
·
Addition
·
Multiplication
After defining the
multiplication operation, elements of the field 
can be raised to a power using the standard binary
exponentiation method in O(log2n) time. This makes it
possible to compute .
Example
In the first example
= 
= 
Let us consider the second
example:
Let x = 
. We’ll compute its powers
step by step:
x2 = 
= 
= 
x4 = 
= 
= 
x8 = 
= 
= 
Now we can compute the
result:
x10 = x8 ∙ x2 =
=
(168 + 
+ 
+ 360) 
= 1 + 
Algorithm implementation
Let us define a structure Num
to store numbers of the form 
.
struct Num
{
long long x, y; // x + y*sqrt(c)
};
Let’s implement multiplication in the field . The function mult
returns the product of two numbers a and b.
Num mult(Num& a, Num& b)
{
Num res;
res.x = (a.x * b.x + c * a.y % p * b.y) % p;
res.y = (a.x * b.y + a.y * b.x) % p;
return res;
}
The function pow implements exponentiation, computing basen,
where base is a number in the field .
Num pow(Num base, long long n)
{
Num res = { 1, 0 };
while (n > 0)
{
if (n & 1)
res
= mult(res, base);
base = mult(base, base);
n >>= 1;
}
return res;
}
The main part of the program. Read the input data.
scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n,
&p);
Initialize the starting number start = 
.
Num start = { a % p, b % p };
Compute and print the answer ans = startn mod p
= .
Num ans = pow(start, n);
printf("%lld %lld\n", ans.x, ans.y);